[Day18] Clojure - Laziness (2) Recursive function & Fibonacci sequence

用Laziness挑戰遞迴 / 費波那契數列

今天剛跑完全程山路有點輕越野路線的烏來峽谷馬拉松
就接著來挑戰這麼hard core的主題，
真的是很Inronman精神啊！

（感動～～42k完賽了！）

自己是Functional programming的新手，
加上也要一邊絞盡腦汁地想怎麼深入淺出引導大家～
內容若有不足，再請前輩們多多指教囉 m(_ _)m

先從我們熟知的Iteration講起好了

之前在講Clojure跟Flow Control的語法時，提到常見的迭代有

• 第11天的for
• 第12天的while

另外repeat也是很好的範例喔

repeat

(repeat x)(repeat n x)

Returns a lazy sequence(infinite!, or length n if supplied) of xs.

舉個例子來看看:

(take 3 (repeat "重要的事情要說3次!"))

=> ("重要的事情要說3次!" "重要的事情要說3次!" "重要的事情要說3次!")

這裡的take

take

(take n)(take n coll)

Returns a lazy sequence of the first n items in coll, 
or all items if there are fewer than n. 
Returns a stateful transducer when no collection is provided.

有了昨天對lazy的解釋

是不是對repeat會把element做 lazy sequence回傳或者take會把collection前n個item 作為lazy sequence回傳這樣的解釋，有更深一層領悟呢?

(take 3 (repeat "重要的事情要說3次!"))

可以寫成

(repeat 3 "重要的事情要說3次")

Recursion遞迴 vs. Iteration 迭代

簡單地又帶了幾個還沒見過，但一下就可以掌握的iteration好用API，
接下來就要談談recursion囉!

• Iteration：用迴圈去循環重複跑某部分的程式碼來求值
• Recursion：重複呼叫自己的function來求值

那為什麼我們要學遞迴呢？

有Recursion的思維，就不怕n是無限大～～

對於無法找到初始的已知部分，

遞迴常用於協助我們找出縮小問題範疇的規律，，
以此規律重複用相同手法來縮減問題範圍，最後找到確定值。

此外學會遞迴，我們也更增進抽象化問題（而非每次都用暴力的迴圈XD），
而且會覺得自己變得更聰明、考試都考100分！

拆解遞迴: 以階乘factorial為例

遇到遞迴問題，可以分成

-確定遞迴的規律部分
-確定遞迴的終止條件

例如常見的階乘factorial (eg. 5! = 5 * 4 * 3 * 2 * 1)

我們發現

• 遞迴的規律部分是階層往下遞減， f(n)= n * (n-1)
• 終止條件 1! = 1; 但數學上規定0的階層也是1 (0! = 1) ，終止條件是到0為止 f(n) = 1

來用熟悉的javascript

function factorial(n)
{
    if (n == 0)   
      return 1; //終止條件
    else 
      return n * factorial(n - 1);
}

factorial(5)
=> 120

factorial(10)
=> 3628800

用clojure的if寫寫看

(defn factorial [n]

  (if (= n 0) 1
      (* n (factorial (- n 1)))))

;;
(factorial 10)

=> 3628800

當然，不管用什麼語言寫

結果都是3628800!!!

真是嚇死人惹！！！

n值才10而已，結果就爆增成這樣

可別忘了昨天提到O(n!)的時間複雜度是很驚人的：）

趕快來學比較沒這麼恐怖的費布納西數列 Fibonacci壓壓驚吧～ （好像沒有安慰到大家XD）

在Clojure裡產生Lazy Fibonacci sequences

Fibonacci sequence又稱為費式數列（義大利語：Successione di Fibonacci）、黃金分割數列

由0和1開始為起始，後面的數字由之前的兩數相加而得出。

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610...

第1個數字: 0
第2個數字: 1
第3個數字: 0 + 1 (第2個數字 + 第1個數字)= 1
第4個數字: 1 + 1 (第3個數字 + 第2個數字)= 2

依此類推

第n個數字: (第n-1個數字 + 第n-2個數字)

用第13天介紹過的Flow control條件式case其實也是可以表達的出來費氏數列

(defn fib [n]
  (case n
    0 0
    1 1

    (+ (fib (- n 1)) (fib (- n 2))))

但因為case並不是lazy sequence系列的一員！
所以為了要懶一下，我們再多做點功課～
work harder so next time we can be lazy and smart

練習1. iterate API 產生Lazy Fibonacci sequences

iterate usage

iterate 

(iterate f x)

Returns a lazy sequence of x, (f x), (f (f x)) etc. 
f must be free of side-effects

看了以上的使用說明，可以知道當call lazy sequence時，
會回傳 10, (inc 10), (inc (inc 10)),...一直往上遞增

(iterate inc 10)
( 10 11 12 13 14 15 ... n ...

因為沒有設停止點，所以電腦風扇又起飛了 XD OutOfMemoryError

iterate 搭配 take

(iterate inc 10)

Error printing return value (OutOfMemoryError) at java.util.Arrays/copyOf (Arrays.java:3332).
Java heap space

用文章開頭介紹的take可以避免貪心造成無窮迴圈的狀況

;; 我不貪心，只拿5個就好

(take 5 (iterate inc 10))
=> (10 11 12 13 14)

實作iterate列出 fibonacci sequance

先把歸納的小抄準備好

第n個數字: (第n-2個數字 + 第n-1個數字)

實作自己的fabonacci-add function

假設我們把要相加的兩個數字放入vector

第一回合 [before after]
第二回合 [after (+before after)]

因此自製費式加法長這樣⬇️

(defn fibonacci-add [[before after]]
  [after (+ before after)]
)

有了自製加法fibonacci-add這個function，
就可以透過def 一個special form
來對某個vector做特別的事情special service evaluated

(def fibonacci-seq
  (map last(iterate fibonacci-add [0 1]))
)

(take 10 fibonacci-seq)

我們知道iterate的作用是不停的對起始值 [0, 1] 做迭代

• [0 1],
• (fibonacci-add [0 1]), evaluate結果為 [1 1]
• (fibonacci-add (fibonacci-add [0 1])) , evaluate結果為 [1 2]
• (fibonacci-add(fibonacci-add (fibonacci-add [0 1]))) , evaluate結果為 [2 3]

來看看這個型別，是屬於 clojure.lang.Iterate

(class(iterate fibonacci-add [0 1]))
=> clojure.lang.Iterate

用last 拿出最後一個值 (型別java.lang.Long)

(class(last [1 2 3 4 5]))
=> java.lang.Long

再用map轉成lazy sequence:

(class (map last(iterate fibonacci-add [0 1])))
;;終於把主角LazySeq的型別轉出來了
=> clojure.lang.LazySeq

• 來執行看看最終結果:

(def fibonacci-seq
  (map last(iterate fibonacci-add [0 1]))
)

(take 15 fibonacci-seq)
=> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)

練習2. 實作lazy-seq列出 fibonacci sequance

昨天發現Flow control分類裡的API有個分類叫做 Laziness

那就拿lazy-seq來用用看吧

lazy-seq 產生Lazy Fibonacci sequences

首先來看看 lazy-seq的用法：

lazy-seq

(lazy-seq & body)

Takes a body of expressions that returns an ISeq or nil, 

and yields a Seqable object that will invoke the body only the first time seq
is called, 

and will cache the result and return it on all subsequent seq calls. 

See also - realized?

realized? 又出現了 好在我們昨天已經理解過一輪了

列出兩種寫法:

• 呼叫時用 take 搭配 defn get-fib-seq

(defn get-fib-seq
         ([]
           (get-fib-seq 1 1))
         ([before after]
           (lazy-seq (cons before (get-fib-seq after (+ before after))))))
;;
(take 15 (get-fib-seq))
=>(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)

• 直接在實作get-fib-seq時用take，使用時直接呼叫 get-fib-seq function

(defn get-fib-seq [n]
  (let [lazy-fib-seq
  ((fn get-seq  [before after]
      (lazy-seq (cons before (get-seq after (+ before after))))
  ) 0 1)]
  (rest (take (+ n 1) lazy-fib-seq)))
)

;;
(get-fib-seq 15)
=> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)

(defn get-fib-seq [n]
  (let [lazy-fib-seq
  ((fn get-seq  [before after]
      (lazy-seq (cons before (get-seq after (+ before after))))
  ) 0 1)]
  (->> lazy-fib-seq (drop 1) (take n)))
)

;;
(get-fib-seq 15)
=> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)

結論

網路上還有很多寫法，可以自行比較使用不同API的差別和特點
了解了recursive function，你就可以成為functional programming的鐵人ironman啦！

Ref:

• 3 ways to generate Lazy Fibonacci sequences in Clojure
  https://blog.klipse.tech/clojurescript/2016/04/19/fibonacci.html

• Generating the Fibonacci Sequence in Clojure
  https://yankev.github.io/2017/05/15/fib_clj.html